#define _CRT_SECURE_NO_WARNINGS

//#include <iostream>
//#include<vector>
//using namespace std;
//
//const int N = 1e3 + 10;
//int a[N][N];
//long long a[N][N];
//
//int main()
//{
//    int n, m;
//    scanf("%d %d", &n, &m);
//    
//
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++) cin >> a[i][j];
//    }
//
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//                   
//        }
//    }
//
//    return 0;
//}

//#include<iostream>
//
//using namespace std;
//
//int main()
//{
//	int s;
//	cin >> s;
//	if (s >= 200 && s <= 299) cout << "Success" << '\n';
//	else cout << "Failure" << '\n';
//
//	return 0;
//}

//#include<iostream>
//#include<string>
//#include<vector>
//using namespace std;
//
//bool kk = 0;
//bool pp = 0;
//
//int main()
//{
//	int count = 0;
//	int cnt = 0;
//	int n;
//	cin >> n;
//	vector<string> ret;
//	int a = 0;
//
//	while (n--)
//	{
//		string s;
//		cin >> s;
//		if (s == "private") a++;
//		ret.push_back(s);
//	}
//
//
//	int m = ret.size();
//	int k = 0;
//	int p = 0;
//	
//	for (int i = 0; i < m; i++)
//	{
//		if (ret[i] == "login")
//		{
//			k = i;
//			kk = true;
//		}
//		else if (ret[i] == "logout")
//		{
//			p = i;
//			pp = true;
//		}
//		if (kk && pp)
//		{
//			for (int j = k + 1; j <= p - 1; j++)
//			{
//				if (ret[j] == "private") a--;
//			}
//			kk = false;
//			pp = false;
//		}
//	}
//	cout << a << '\n';
//
//	return 0;
//}

#include<iostream>

using namespace std;

const int N = 1e6 + 10;
long long a[N];
const int M = 1e9;

int main()
{
	int n, k;
	cin >> n >> k;
	
   
	for (int i = 0; i < n+1;i++)
	{
		if (i < k)
		{
			a[i] = 1;
		}
		else if(i >= k)
		a[i] = (a[i - 1] + a[i - 2]) % M;
	}
	cout << a[n] % M << '\n';

	return 0;
}